package LeetCode;

import java.util.HashMap;
import java.util.Map;

public class Code322_coinChange {
//    // 动态规划，个数最少的背包问题
//    public int coinChange(int[] coins, int amount) {
//        if (coins == null || coins.length == 0){
//            return 0;
//        }
//
//    }
    // 递归，个数最小目标和（超时）
    int[] coins;
    Map<Integer, Integer> map = new HashMap<>();
    public int coinChange(int[] coins, int amount) {
        if (coins == null || coins.length == 0){
            return -1;
        }
        this.coins = coins;
        return dfs(amount);
    }

    private int dfs(int target) {
        if (map.containsKey(target)){
            return map.get(target);
        }
        if (target == 0){
            return 0;
        }
        int res = Integer.MAX_VALUE;
        for (int coin : coins){
            if (target - coin >= 0){
                int temp = dfs(target - coin);
                if (temp == -1){ // 当前元素子树没有符合条件的，更换当前元素，遍历下一个
                    continue;
                }
                res = Math.min(res, temp + 1);
            }
        }
        res = res == Integer.MAX_VALUE ? -1 : res;
        map.put(target, res);
        return res;
    }

    // 动态规划
    public int coinChange2(int[] coins, int amount) {
        if (coins == null || coins.length == 0){
            return -1;
        }
        // dp[i]是组成i的最小个数
        int[] dp = new int[amount + 1];
        for (int i = 1; i <= amount; i++) {
            dp[i] = Integer.MAX_VALUE;
            for (int coin : coins) {
                if (i - coin >= 0 && dp[i - coin] != Integer.MAX_VALUE) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }

    public static void main(String[] args) {
        int[] arr = new int[]{2};
        Code322_coinChange code322_coinChange = new Code322_coinChange();
        System.out.println(code322_coinChange.coinChange2(arr, 3));
    }
}
